#include "../../lib/common.h"
#define N 10

int binary_search(const int *arr, const int n, const int target); // 二分查找
int binary_search2(const int *arr, const int n, const int target); // 二分查找

int main(void)
{
  int arr[N] = {1, 3, 6, 8, 12, 15, 23, 26, 31, 35};
  int index = binary_search(arr, N, 6);
  printf("%d\n", index);
  index = binary_search2(arr, N, 6);
  printf("\n%d\n", index);
  return 0;
}

/**
 * 闭区间写法
 */
int binary_search(const int *arr, const int size, const int target) // 二分查找
{
  int i = 0, j = size - 1; // 首尾索引
  int m; // 中点索引
  while (i <= j)
  {
    // m = (i + j) / 2; // 正整数除法实际上是整除
    // 两个int相加可能会造成结果超过int的最大范围
    m = i + (j - i) / 2;
    if (arr[m] < target) i = m + 1; // target在有半段
    else if (arr[m] == target) return m; // target刚好在中点
    else j = m - 1; // target在左半段  
  }
  return -1;
}

/**
 * 左闭右开区间写法
 */
int binary_search2(const int *arr, const int size, const int target) // 二分查找
{
  int i = 0, j = size; // 首尾索引
  int m; // 中点索引
  while (i < j)
  {
    // m = (i + j) / 2; // 正整数除法实际上是整除
    // 两个int相加可能会造成结果超过int的最大范围
    m = i + (j - i) / 2;
    if (arr[m] < target) i = m + 1; // target在右半段
    else if (arr[m] == target) return m; // target刚好在中点
    else j = m; // target在左半段  
  }
  return -1;
}